package org.xiaojinlong.algo;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Jin Long
 * 2015/9/1
 */
public class RelativeSort {
    private static class Element {
        Comparable value;
        int index;
        Stack<Element> pair = new ResizingArrayStack<>();
    }

    static void relativeSort(Comparable[] a) {
        Element[] A = new Element[a.length];
        Element[] B = new Element[a.length];

        for (int i = 0; i < a.length; i++) {
            A[i] = new Element();
            A[i].value = a[i];
        }

        sort(A, 0, a.length - 1, B);

        for (int i = 0; i < a.length; i++)
            a[i] = A[i].value;
    }

    private static void sort(Element[] a, int lo, int hi, Element[] b) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        for (int i = 0, j = mid + 1; i <= mid; i++, j++) {
            if (less(a[j].value, a[i].value)) {
                Element swap = a[j];
                a[j] = a[i];
                a[i] = swap;
                a[j].pair.push(a[i]);
            } else
                a[j].pair.push(a[i]);
        }
        sort(a, lo, mid, b);
        sort(a, mid + 1, hi, b);

        for (int i = lo; i <= mid; i++)
            a[i].index = i;

        merge(a, lo, mid, hi, b);
    }

    private static void merge(Element[] a, int lo, int mid, int hi, Element[] b) {
        int pairIndex = a[mid + 1].pair.pop().index; // first
        int high = pairIndex + 1;
        int i = high;
        Element latest = b[mid + 1];

        System.arraycopy(a, high, b, high, hi - high + 1);

        for (int j = mid + 2; j <= hi; j++) {
            pairIndex = b[j].pair.pop().index;
            if (pairIndex >= high) {
                boolean found = false;
                int mark = 0;
                for (int k = high; k <= pairIndex; k++) {
                    if (less(latest.value, b[k].value)) {
                        found = true;
                        mark = k;
                        break;
                    }
                }
                if (found) {
                    System.arraycopy(b, high, a, i, mark - high);
                    i = i + mark - high;
                    a[i] = latest;
                    i++;
                    high = high + mark - high;
                    System.arraycopy(b, high, a, i, pairIndex - high + 1);
                    i = i + pairIndex - high + 1;
                    high = pairIndex + 1;
                } else {
                    System.arraycopy(b, high, a, i, pairIndex - high + 1);
                    i = i + pairIndex - high + 1;
                    high = pairIndex + 1;
                    a[i++] = latest;
                }
                latest = b[j];
            } else {
                a[i++] = latest;
            }
        }

        a[i] = b[hi];
    }

    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    public static void main(String[] args) {
        Integer[] integers = new Integer[100];
        Random random = new Random();
        for (int i = 0; i < 100; i++)
            integers[i] = random.nextInt(100);
        System.out.println(Arrays.toString(integers));
        relativeSort(integers);
        System.out.println(Arrays.toString(integers));
    }
}
